import java.lang.reflect.Array;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        solution.validPalindrome("abc");
//        int[] nums = {-1,0,1,2,-1,-4};
//        System.out.println(solution.threeSum(nums));
//        solution.compareVersion("1.2", "1.10");
//        solution.lengthOfLongestSubstring("bbbbb");
//        System.out.println(solution.getRow(3));
//        System.out.println(solution.findAnagrams("cbaebabacd", "abc").toString());
        solution.characterReplacement("BAAA", 0);
        int[] nums = {1,3,-1,-3,5,3,6,7};
        System.out.println(Arrays.toString(solution.maxSlidingWindow(nums, 3)));
    }

    // 12.18 题2：求和路径
//    public int pathSum(TreeNode root, int sum) {
//        if (root == null) {
//            return 0;
//        }
//        return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
//    }
//
//    public int dfs(TreeNode root, int sum) {
//        // 递归出口
//        if (root == null) {
//            return 0;
//        }
//        sum -= root.val;
//        return ((sum == 0 ? 1 : 0) + dfs(root.left, sum) + dfs(root.right, sum));
//    }

    // 12.18 题1：检查子树
//    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
//        if (t1 == null) {
//            return false;
//        }
//        return isSameTree(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
//    }
//
//    // 判断是否是相同的两棵树
//    public boolean isSameTree(TreeNode t1, TreeNode t2) {
//        if (t1 == null && t2 == null) {
//            return true;
//        }
//        if (t1 == null || t2 == null) {
//            return false;
//        }
//        return (t1.val == t2.val && isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right));
//    }

    // 12.17 题2：排序矩阵查找
    public boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix == null) return false;
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;
        int i = 0, j = n - 1;
        while(i < m && j >= 0) {
            if (matrix[i][j] < target) {
                i++;
            } else if (matrix[i][j] > target) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }

    // 12.17 题1：消失的数字
    public int missingNumber(int[] nums) {
        int sum = 0;
        int len = nums.length;
        for(int i = 1; i <= len; i++) {
            sum += i;
        }
        for(int i = 0; i < len; i++) {
            sum -= nums[i];
        }
        return sum;
    }

    // 12.16 题2：搜索二维矩阵ii
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        for(int i = 0; i < m; i++) {
            // 每一行依次判断
            if(target < matrix[i][0]) {
                return false;
            } else if (target >= matrix[i][0] && target <= matrix[i][n - 1]) { // 是否可能在该行
                // 二分查找
                boolean flg = BinarySearch(matrix, i, n - 1,target);
                if (flg) {
                    return true;
                }
            }
        }
        return false;
    }
    // 二分查找
    public boolean BinarySearch(int[][] nums, int i, int end, int target) {
        if (target < nums[i][0] || target > nums[i][end]) {
            return false;
        }
        if(target == nums[i][0] || target == nums[i][end]) {
            return true;
        }
        int left = 0;
        int right = end;
        while(left < right) {
            int mid = (left + right) / 2;
            if (nums[i][mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[i][left] == target;
    }

    // 12.16 题1：判定是否互为字符重排
    public boolean CheckPermutation(String s1, String s2) {
        // 判断两字符串是否相同
        if(s1.length() != s2.length()) {
            return false;
        }
        int[] hash = new int[26];
        int[] hash2 = new int[26];
        for(int i = 0; i < s1.length(); i++) {
            hash[s1.charAt(i) - 'a']++;
        }
        for(int i = 0; i < s2.length(); i++) {
            hash2[s2.charAt(i) - 'a']++;
        }
        for(int i = 0; i < 26; i++) {
            if(hash[i] != hash2[i]) {
                return false;
            }
        }
        return true;
    }

    // 12.15 题3: 多次搜索
    // kmp
    public int[][] multiSearch(String big, String[] smalls) {
        int[][] res = new int[smalls.length][];
        for(int i = 0; i < smalls.length; i++) {
            if(smalls[i].equals("") || big.equals("")) {
                res[i] = new int[0];
                continue;
            }
            List<Integer> tmp = kmp(big, smalls[i]);
            int[] index = new int[tmp.size()];
            for (int j = 0; j < tmp.size(); j++) {
                index[j] = tmp.get(j);
            }
            res[i] = index;
        }
        return res;
    }
    public List<Integer> kmp(String str, String target) {
        List<Integer> res = new ArrayList<>();
        // 处理特殊情况
        if(str == null || target == null) {
            return res;
        }
        int strLen = str.length();
        int targetLen = target.length();
        if(strLen == 0 || strLen < targetLen) {
            return res;
        }
        // 计算 next 数组
        int[] next = new int[targetLen + 1];
        getNext(next, target);
        // 判断
        int i = 0, j = 0;
        while (i < strLen) {
            if (j == -1 || str.charAt(i) == target.charAt(j)) {
                i++;
                j++;
                // 匹配成功
                if(j == targetLen) {
                    res.add(i - j);
                    j = next[j];
                }
            } else {
                j = next[j];
            }
        }
        return res;
    }

    private void getNext(int[] next, String target) {
        if(target == null) {
            return;
        }
        int len = next.length;
        if (len == 0) {
            return;
        }
        next[0] = -1;
        int j = 0, k = -1;
        while (j < len - 1) {
            if (k == -1 || target.charAt(j) == target.charAt(k)) {
                j++;
                k++;
                if (j != target.length() && target.charAt(j) == target.charAt(k)) {
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
            } else {
                k = next[k];
            }
        }
    }

    // 12.15 题2：滑动窗口最大值
    // 单调队列 + 滑动窗口
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[nums.length - k + 1];
        // 处理前 k 个元素
        for(int i = 0; i < k - 1; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.addLast(i);
        }
        // 维护队列
        for(int left = 0, right = k - 1; left < res.length; left++, right++) {
            // 将小于 nums[right] 的元素弹出队列
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[right]) {
                deque.pollLast();
            }
            // 将 nums[right] 加入队列
            deque.offerLast(right);
            // 将结果加入 res 中
            res[left] = nums[deque.peekFirst()];
            // 判断是否需要弹出元素
            if(!deque.isEmpty() && deque.peekFirst() == left) {
                deque.pollFirst();
            }
        }
        return res;
    }


    // 12.15 题1 二叉树的右视图
    // 层序遍历
//    public List<Integer> rightSideView(TreeNode root) {
//        List<Integer> res = new ArrayList<>();
//        if(root == null) {
//            return res;
//        }
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.add(root);
//        while(!queue.isEmpty()) {
//            int len = queue.size();
//            for(int i = 0; i < len; i++) {
//                TreeNode node = queue.poll();
//                if (node.left != null) {
//                    queue.add(node.left);
//                }
//                if (node.right != null) {
//                    queue.add(node.right);
//                }
//                if(i == len - 1) {
//                    res.add(node.val);
//                }
//            }
//        }
//        return res;
//    }
//
    // 12.9 将字符串翻转到单调递增
    public int minFlipsMonoIncr(String s) {
        char[] chs = s.toCharArray();
        int len = chs.length;
        // dp[i][0]: 将 i 位置翻转为 0 时的最小翻转次数
        // dp[i][1]: 将 i 位置翻转为 1 时的最小翻转次数
        int[][] dp = new int[len][2];
        if (chs[0] == '0') {
            dp[0][1] = 1;
        } else {
            dp[0][0] = 1;
        }
        for(int i = 1; i < len; i++) {
            // i 位置为 1
            if (chs[i] == '1') {
                dp[i][0] = dp[i - 1][0] + 1;
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
            } else {
                // i 位置为 0
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
            }
        }
        return Math.min(dp[len - 1][0], dp[len - 1][1]);
    }

    // 12.9 替换后的最长重复字符
    public int characterReplacement(String s, int k) {
        int[] hash = new int[26];
        char[] chs = s.toCharArray();
        int maxCount = 0;
        int left = 0, right = 0;
        for(; right < chs.length; right++) {
            // 进窗口
            int index = chs[right] - 'A';
            hash[index]++;
            // 计算区间内的最长重复字符
            maxCount = Math.max(hash[index], maxCount);
            // 判断是否需要出窗口
            if(right - left + 1 - maxCount > k) {
                int out = chs[left] - 'A';
                hash[out]--;
                left++;
            }
        }
        return right - left;
    }

    // 12.8 (1) 数组中两元素的最大乘积
    public int maxProduct(int[] nums) {
        int n1 = Math.max(nums[0], nums[1]);
        int n2 = Math.min(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++) {
            if(nums[i] > n1) {
                n2 = n1;
                n1 = nums[i];
            } else if(nums[i] > n2) {
                n2 = nums[i];
            }
        }
        return (n1 - 1) * (n2 - 1);
    }
    // 12.7 (2) 水果成篮
    public int totalFruit(int[] fruits) {
        int maxCount = 0;
        Map<Integer, Integer> hash = new HashMap<>();
        for(int left = 0, right = 0; right < fruits.length; right++) {
            // 进窗口
            hash.put(fruits[right], hash.getOrDefault(fruits[right], 0) + 1);
            // 判断是否需要出窗口
            while(hash.size() > 2 && left < right) {
                if(hash.get(fruits[left]) == 1) {
                    hash.remove(fruits[left]);
                } else {
                    hash.put(fruits[left], hash.get(fruits[left]) - 1);
                }
                left++;
            }
            // 更新结果
            maxCount = Math.max(maxCount, right - left + 1);
        }
        return maxCount;
    }

    // 12.7 (1) 按奇偶排序数组
    public int[] sortArrayByParity(int[] nums) {
        int right = -1;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] % 2 == 0) {
                int tmp = nums[++right];
                nums[right] = nums[i];
                nums[i] = tmp;
            }
        }
        return nums;
    }
    // 12.6 (2) 找到字符串中的所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        char[] hash = new char[26];
        char[] hash2 = new char[26];
        for(char ch: p.toCharArray()) {
            hash[ch - 'a']++;
        }
        List<Integer> res = new ArrayList<>();
        char[] chs = s.toCharArray();
        int count = 0;
        for(int left = 0, right = 0; right < s.length(); right++) {
            // 进窗口
            int in = chs[right] - 'a';
            if (++hash2[in] <= hash[in]) {
                count++;
            }
            // 判断
            if(right - left + 1 > p.length()) {
                int out = chs[left++] - 'a';
                if(hash2[out]-- <= hash[out]) {
                    count--;
                }
            }
            // 更新结果
            if (count == p.length()) {
                res.add(left);
            }
        }
        return res;
    }
    // 12.6 (1) 杨辉三角II
    public List<Integer> getRow2(int rowIndex) {
        int[] res = new int[rowIndex + 1];
        for(int i = 0; i <= rowIndex; i++) {
            for(int j = i; j >= 0; j--) {
                if (j == 0 || j == i) {
                    res[j] = 1;
                } else {
                    res[j] += res[j - 1];
                }
            }
        }
        List<Integer> ret = new ArrayList<>();
        for(int i = 0; i <= rowIndex; i++) {
            ret.add(res[i]);
        }
        return ret;
    }
    public List<Integer> getRow(int rowIndex) {
        List<Integer> prev = new ArrayList<>();
        for(int i = 0; i <= rowIndex; i++) {
            List<Integer> cur = new ArrayList<>();
            for(int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(prev.get(j - 1) + prev.get(j));
                }
            }
            prev = cur;
        }
        return prev;
    }

    // 最小覆盖子串
    public String minWindow(String s, String t) {
        char[] chs = s.toCharArray();
        char[] cht = t.toCharArray();
        char[] hash1 = new char[128];
        char[] hash2 = new char[128];
        for(char ch: cht) {
            hash1[ch]++;
        }
        int begin = 0, len = Integer.MAX_VALUE, count = 0;
        for(int left = 0, right = 0; right < chs.length; right++) {
            // 进窗口
            int in = chs[right];
            hash2[in]++;
            if (hash2[in] <= hash1[in]) {
                count++;
            }
            // 出窗口
            while (count >= cht.length) {
                // 更新结果
                if (count == cht.length && right - left + 1 < len) {
                    begin = left;
                    len = right - left + 1;
                }
                // 出窗口
                int out = chs[left];
                if (hash2[out] <= hash1[out]) {
                    count--;
                }
                hash2[out]--;
                left++;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(begin, begin + len);
    }

    // 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        char[] chs = s.toCharArray();
        int maxCount = 0;
        char[] hash = new char[128];
        for(int left = 0, right = 0; right < chs.length; right++) {
            // 入窗口
            hash[chs[right]]++;
            // 出窗口
            if(hash[chs[right]] != 0) {
                // 出窗口
                while(left < right && hash[chs[right]] > 1) {
                    hash[chs[left]]--;
                    left++;
                }
            }
            // 计算
            maxCount = Math.max(maxCount, right - left + 1);
        }
        return maxCount;
    }

    // 12.5(1) 有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char ch: s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.empty()) {
                    return false;
                }
                char left = stack.pop();
                if (!((left == '(' && ch == ')') || (left == '[' && ch == ']') || (left == '{' && ch == '}'))) {
                    return false;
                }
            }
        }
        return stack.empty();
    }

    // 12.4 (1) 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i = nums.length - 1; i > 1; i--) {
            int left = 0, right = i - 1;
            int target = -nums[i];
            while(left < right) {
                if (nums[left] + nums[right] < target) {
                    left++;
                } else if (nums[left] + nums[right] > target) {
                    right--;
                } else {
                    List<Integer> tmp = new ArrayList<>(Arrays.asList(nums[left], nums[right], nums[i]));
                    res.add(tmp);
                    left++;
                    right--;
                    // 去重
                    while(left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
            // 去重
            while(i > 1 && nums[i - 1] == nums[i]) {
                i--;
            }
        }
        return res;
    }

    // 12.4 (2) 比较版本号
    // 双指针
    public int compareVersion2(String version1, String version2) {
        int i = 0, j = 0;
        char[] v1 = version1.toCharArray();
        char[] v2 = version2.toCharArray();
        while(i < v1.length || j < v2.length) {
            int count1 = 0, count2 = 0;
            while(i < v1.length && v1[i] != '.') {
                count1 = count1 * 10 + (v1[i] - '0');
                i++;
            }
            while(j < v2.length && v2[j] != '.') {
                count2 = count2 * 10 + (v2[j] - '0');
                j++;
            }
            if (count1 > count2) {
                return 1;
            } else if (count2 > count1) {
                return -1;
            }
            i++;
            j++;
        }
        return 0;
    }
    // 字符串分割
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        for (int i = 0; i < v1.length || i < v2.length; i++) {
            // 获取两个版本的修订号
            int count1 = 0, count2 = 0;
            if (i < v1.length) {
                count1 = Integer.parseInt(v1[i]);
            }
            if (i < v2.length) {
                count2 = Integer.parseInt(v2[i]);
            }
            if (count1 > count2) {
                return 1;
            } else if (count1 < count2) {
                return -1;
            }
        }
        return 0;
    }

    // 12.3 (1) 二叉树的前序遍历
    // 递归
//    List<Integer> res;
//    public List<Integer> preorderTraversal(TreeNode root) {
//        res = new ArrayList<>();
//        preorder(root);
//        return res;
//    }
//
//    public void preorder(TreeNode root) {
//        if (root == null) {
//            return;
//        }
//        res.add(root.val);
//        preorder(root.left);
//        preorder(root.right);
//    }
    // 非递归
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> res = new ArrayList<>();
//        if (root == null) {
//            return res;
//        }
//        Stack<TreeNode> stack = new Stack<>();
//        stack.push(root);
//        while(!stack.empty()) {
//            TreeNode cur = stack.pop();
//            res.add(cur.val);
//            if (cur.right != null) stack.push(cur.right);
//            if (cur.left != null) stack.push(cur.left);
//        }
//        return res;
//    }

    // 字典序最小回文串
    public String makeSmallestPalindrome(String s) {
        char[] chs = s.toCharArray();
        int left = 0;
        int right = chs.length - 1;
        while (left < right) {
            if (chs[left] < chs[right]) {
                chs[right] = chs[left];
            } else {
                chs[left] = chs[right];
            }
            left++;
            right--;
        }
        return new String(chs);
    }

    // 12.2 (1)验证回文串
    // 贪心
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while(left < right) {
            if(s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return (validPalindrome(s, left + 1, right) || validPalindrome(s, left, right - 1));
            }
        }
        return true;
    }

    public boolean validPalindrome(String s, int left, int right) {
        while(left < right) {
            if(s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }


    // 动规(超时)
    public boolean validPalindrome1(String s) {
        int len = s.length();
        s = " " + s;
        int[][] dp = new int[len + 1][len + 1];
        for(int i = len; i >= 1; i--) {
            for(int j = i; j <= len; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if (i != j && i + 1 != j) {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        System.out.println(dp[1][len]);
        return dp[1][len] <= 1;
    }

     // 12.1 (1) 链表中环的入口结点
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        ListNode slow = pHead.next;
        ListNode fast = pHead.next.next;
        // 判断是否有环
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }

        ListNode cur = pHead;
        while(cur != slow) {
            cur = cur.next;
            slow = slow.next;
        }
        return slow;
    }

    // 12.1 (2) 单链表的排序
    // 使用辅助链表排序(超时)
    public ListNode sortInList (ListNode head) {
        // write code here
        ListNode newHead = new ListNode(0);
        ListNode cur = head;
        while(cur != null) {
            findIndex(cur.val, newHead);
            cur = cur.next;
        }
        return newHead.next;
    }
    public void findIndex(int val, ListNode head) {
        ListNode cur = head;
        ListNode node = new ListNode(val);
        // 头插
        if(head.next == null || head.next.val >= val) {
            node.next = head.next;
            head.next = node;
            return;
        }
        // 中间
        while(cur != null && cur.next != null) {
            if (cur.val <= val && cur.next.val >= val) {
                node.next = cur.next;
                cur.next = node;
                return;
            }
            cur = cur.next;
        }
        // 尾插
        cur.next = node;
    }

    // 单链表的排序(使用辅助数组)
    public ListNode sortInList2 (ListNode head) {
        // write code here
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        list.sort((a, b) -> a-b);
        cur = head;
        int i = 0;
        while(cur != null) {
            cur.val = list.get(i++);
            cur = cur.next;
        }
        return head;
    }

    // 单链表的排序(归并)
    public ListNode sortInList3 (ListNode head) {
        // write code here
        if(head == null || head.next == null) {
            return head;
        }
        // 找到中点
        ListNode slow = head, fast = head.next;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 分割为两个链表
        ListNode node = slow.next;
        slow.next = null;
        // 继续分割
        ListNode left = sortInList(head);
        ListNode right = sortInList(node);
        // 合并(尾插)
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;
        while(left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left == null ? right: left;
        return newHead.next;
    }

    // 11.30 (2) 合并区间
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        // write code here
        ArrayList<Interval> res = new ArrayList<>();
        if(intervals == null || intervals.size() == 0) {
            return res;
        }
        // 按 start 升序排列
        intervals.sort((v1, v2) ->{
            if(v1.start == v2.start) {
                return v1.end - v2.end;
            }
            return v1.start - v2.start;
        });
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        // 合并区间
        for(int i = 1; i < intervals.size(); i++) {
            if(end < intervals.get(i).start) {
                res.add(new Interval(start, end));
                start = intervals.get(i).start;
                end = intervals.get(i).end;
            } else {
                end = Math.max(end, intervals.get(i).end);
            }
        }
        res.add(new Interval(start, end));
        return res;
    }

}

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}

class Interval {
    int start;
    int end;
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
 }
